/*
 * @Author: 缄默
 * @Date: 2022-03-14 22:30:28
 * @LastEditors: 缄默
 * @LastEditTime: 2022-03-16 21:10:52
 */

//判断字符串中是否所有的字符只出现过一次
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

//时间复杂度O(n)
bool isUnque1(const string& s1);

//空间复杂度O（1）
bool isUnque2(const string& s1);
//非递归的堆排序
void heapSort(string& s1);
void filterDown(int i, int size, string& s1);
int main() {
    string s1 = "abcd";
    string s2 = "abbc";
    cout << "O(n): " << isUnque1(s1) << "   " << isUnque1(s2) << endl;
    cout << "O(1): " << isUnque2(s1) << "   " << isUnque2(s2) << endl; 

    return 0;
}

bool isUnque1(const string& s1) {
    map <char, bool> hashmap;
    for (auto chr : s1) {
        if (hashmap.count(chr) == 1) {
            return false;
        }
        else {
            hashmap[chr] = true;
        }
    }

    return true;
}

bool isUnque2(const string& s2) {
    // 实现空间复杂度O（1）的算法
    //先排序，相邻相同即不符合  选择空间复杂度O（1）的排序算法 堆排序 非递归
    string s1 = s2;
    heapSort(s1);
    for (int i = 1; i < s1.size(); i++) {
        if (s1[i] == s1[i - 1]) return false;
    }
    return true;
}

//堆排序
void heapSort(string& s1) {

    //1. 建立大顶堆
    for (int i = s1.size() / 2 - 1; i >=0; i--) {
        filterDown(i , s1.size(), s1);
    }

    //2. 调整堆结构+交换堆顶元素与末尾元素
    for (int i = s1.size() - 1; i > 0; i--) {
        swap(s1[i], s1[0]);
        filterDown(0, i, s1);
    }


}

//堆结构的调整是自顶向下的，从输入位置i开始调整，末尾位置为size
//从上向下判断s1[i]真正应该在的位置
void filterDown(int i, int size, string& s1) {
    int tmp = s1[i];
    for (int k = i * 2 + 1; k < size; k++)  {
        //比较两个子节点的大小
        if (k + 1 < size && s1[k] < s1[k + 1]) {
            k++;
        }
        //子节点最大的与s1[i]比较 交换过后开始以k为节点向下比较
        if (s1[k] > tmp) {
            s1[i] = s1[k];
            //i记录当前比较的是那个元素
            i = k;
        }
        //之前构建过大顶堆 因此一次比较发现不用调整，则结束循环
        else {
            break;
        }
    }
    //比较过后在将tmp赋值给s1[i]
    s1[i] = tmp;
    
    return ;

}
